%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\chapter{Building graphs without properties}
\label{sec:Building-graphs-without-properties}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Boost.Graph is about creating graphs.
In this chapter we create the simplest of graphs, in which edges and nodes
have no properties (e.g. having a name).

Still, there are two types of graphs that can be constructed: undirected
and directed graphs.
The difference between directed and undirected graphs is in the edges:
in an undirected graph, 
an edge connects two vertices without any directionality, as displayed
in figure \ref{fig:undirected_graph_example}.

In a directed graph, an edge goes from a certain vertex, 
its source, to another (which may actually be the same), its target.
A directed graph is shown in figure \ref{fig:directed_graph_example}.

\begin{figure}
  \begin{tikzpicture}
    \draw[thick] 
      (0,0) node[draw=black,fill=white,shape=circle,text=white] {} 
      -- (5,2) node[draw=black,fill=white,shape=circle,text=white] {} 
      -- (10,1) node[draw=black,fill=white,shape=circle,text=white] {} 
    ;
  \end{tikzpicture}
  \caption{Example of an undirected graph}
  \label{fig:undirected_graph_example}
\end{figure}

\begin{figure}
  \begin{tikzpicture}
    \SetGraphUnit{5}
    \tikzset{VertexStyle/.append style = {draw=black,fill=white,shape=circle,text=white} }
    \Vertex{A}
    \EA(A){B}
    \EA(B){C}
    \tikzset{EdgeStyle/.append style = {->, bend left} }
    \Edge[](A)(B)
    \Edge[](B)(A)
    \Loop[dist = 4cm, dir = NO](A.west)
    \tikzset{EdgeStyle/.append style = {bend left = 0} }
    \Edge[](C)(B)   
  \end{tikzpicture}
  \caption{Example of a directed graph}
  \label{fig:directed_graph_example}
\end{figure}

In this chapter, we will build two directed and two undirected graphs:

\begin{itemize}
  \item An empty (directed) graph, which is the default type: 
    see chapter \ref{subsec:create_empty_directed_graph}
  \item An empty (undirected) graph: 
    see chapter \ref{subsec:create_empty_undirected_graph}
  \item A two-state Markov chain, a directed graph with two vertices 
    and four edges:
    see chapter \ref{subsec:create_markov_chain_graph}
  \item $K_{2}$, an undirected graph with two vertices and one edge, 
    see chapter \ref{subsec:create_k2_graph}
\end{itemize}


Creating an empty graph may sound trivial, it is not, thanks to the versatility
of the Boost.Graph library.

In the process of creating graphs, some basic (sometimes bordering trivial)
functions are encountered:

\begin{itemize}
  \item Counting the number of vertices, 
    see chapter \ref{subsec:get_n_vertices}
  \item Counting the number of edges,
     see chapter \ref{subsec:get_n_edges}
  \item Adding a vertex,
     see chapter \ref{subsec:add_vertex}
  \item Getting all vertices,
     see chapter \ref{subsec:get_vertices}
  \item Getting all vertex descriptors,
     see chapter \ref{subsec:get_vertex_descriptors}
  \item Adding an edge,
     see chapter \ref{subsec:add_edge}
  \item Getting all edges,
    see chapter \ref{subsec:get_edge_iterators}
  \item Getting all edge descriptors,
    see chapter \ref{subsec:get_edge_descriptors}
\end{itemize}

These functions are mostly there for completion and showing which data types
are used.

The chapter also introduces some important concepts:

\begin{itemize}
  \item Vertex descriptors,
    see chapter \ref{subsec:Vertex-descriptors}
  \item Edge insertion result,
    see chapter \ref{subsec:boost::add_edge result}
  \item Edge descriptors,
    see chapter \ref{subsec:Edge-descriptors}
\end{itemize}

After this chapter you may want to:

\begin{itemize}
  \item Building graphs with named vertices, 
    see chapter \ref{sec:Building-graphs-with-named-vertices}
  \item Building graphs with bundled vertices, 
    see chapter \ref{sec:Building-graphs-with-bundled-vertices}
  \item Building graphs with custom vertices,
    see chapter \ref{sec:Building-graphs-with-custom-properties}
  \item Building graphs with a graph name,
    see chapter \ref{sec:Building-graphs-with-a-graph-name}
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Creating an empty (directed) graph}
\label{subsec:create_empty_directed_graph}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Let's create an empty graph! 
Listing \ref{lst:create_empty_directed_graph} shows the function to create an empty graph.

\lstinputlisting[
  caption = Creating an empty (directed) graph,
  label = lst:create_empty_directed_graph
]{create_empty_directed_graph.impl}

